//class Solution {
//public:
//    struct greater
//    {
//        bool operator()(const pair<string, int>& x, const pair<string, int>& y)
//        {
//            return x.second > y.second || (x.second == y.second && x.first < y.first);
//        }
//    };
//    vector<string> topKFrequent(vector<string>& words, int k) {
//        map<string, int> m;
//        for (auto e : words)
//        {
//            m[e]++;
//        }
//        vector<pair<string, int>> v(m.begin(), m.end());
//        sort(v.begin(), v.end(), greater());
//        vector<string> vs;
//        vector<pair<string, int>>::iterator it = v.begin();
//        while (k--)
//        {
//            vs.push_back(it->first);
//            it++;
//        }
//        return vs;
//    }
//};

//#include <atomic>
//#include <iostream>
//#include <map>
//#include <string>
//#include <vector>
//#include <algorithm>
//using namespace std;
//struct Compare {
//    bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
//        return x.second > y.second || (x.second == y.second && x.first < y.first);
//    }
//};
//int main() {
//    string s;
//    while (getline(cin, s)) {
//        for (int i = 0; i < s.size() - 1; i++)
//        {
//            if (s[i] >= 'A' && s[i] <= 'Z')
//            {
//                s[i] += 32;
//            }
//        }
//
//        vector<string> vs;
//        int begin = 0, end = 0;
//        for (end = s.find(' ', begin); end != -1; end = s.find(' ', begin)) {
//            string str(s.begin() + begin, s.begin() + end);
//            vs.push_back(str);
//            begin = end + 1;
//        }
//        string str(s.begin() + begin, s.end() - 1);
//        vs.push_back(str);
//
//        map<string, int> m;
//        for (auto e : vs) {
//            m[e]++;
//        }
//
//        vector<pair<string, int>> v(m.begin(), m.end());
//        sort(v.begin(), v.end(), Compare());
//        for (auto e : v) {
//            cout << e.first << ":" << e.second << endl;
//        }
//    }
//    return 0;
//}
